#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0028.py
@time: 2021/11/5 13:52
@desc:
'''


class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        visited = [[False for i in range(n)] for j in range(m)]

        def s(i, j):
            nums = str(i) + str(j)
            sum = 0
            for num in nums:
                sum += int(num)
            return sum

        def dfs(i, j):
            if not 0 <= i < m or not 0 <= j < n or not s(i, j) <= k or visited[i][j]:
                return 0
            visited[i][j] = True
            res = 1 + dfs(i - 1, j) + dfs(i, j - 1) + dfs(i + 1, j) + dfs(i, j + 1)
            return res

        return dfs(0, 0)


if __name__ == '__main__':
    res = Solution().movingCount(1, 2, 1)
    print(res)
